class code3 {
    //摩尔投票法
    public int majorityElement(int[] nums) {
        int k = 0;//当前数
        int count = 0;//当前个数

        //1.找出众数
        for(int x:nums) {
            if(count == 0) {
                k = x;
                count = 1;
            } else {
                count += (x == k ? 1 : -1);//相同就+1,不同就-1
            }
        }
        //2.统计个数判定
        count = 0;
        for(int x:nums) {
            if(x == k) {
                count++;
            }
        }

        return count>nums.length/2 ? k : -1;
    }
}